import java.util.*;

/**
 * @Author 12629
 * @Description：
 */
public class TestHeap {

    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }

    //初始化数组的
    public void initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

    /**
     * 时间复杂度：O(N)  创建堆的过程 ， 默认创建大根堆
     */
    public void createHeap() {
        for (int parent = (usedSize - 1 - 1) / 2; parent >= 0 ; parent--) {
            shiftDown(parent,usedSize);
        }
    }

    /**
     * 父亲下标
     * 每棵树的结束下标
     *   向下调整的时间复杂度是 树的高度
     * @param parent
     * @param len
     */
    //向下调整：指的是每次父亲节点都是向下面调整
    //  注意这里的parent来接收，只是一个形参，没有影响到原来的parent值
    private void shiftDown(int parent,int len) {
        int child = parent * 2 + 1; //这是左孩子
        //判断左孩子存在条件
        while(child < len) {
            //注意还要进行判断右孩子是否存在
            if (child + 1 < len && elem[child] < elem[child + 1]) {
                child++;
            }
            //走到这里保证child下标 一定是左右 孩子数最大的下标
            if(elem[child] > elem[parent]) {

                //进行交换
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                //交换完之后可能有破坏后面的堆结构，所以继续调整
                parent = child;
                child = parent * 2 + 1;
            }else {
                break;  //或者是return  因为后面出了循环没有代码了
            }
        }
    }

    private void shiftUp(int child) {
        int parent = (child - 1) / 2;
        while (parent >= 0) {
            if(elem[child] > elem[parent]) {
                //进行交换
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child - 1) / 2;
            }else {
                return;
            }
        }
    }

    //向上调整建堆的时间复杂度：N*logN  (一个节点向上调整 树的高度h = log（N + 1） 次，N表示节点 ，共有N个节点)
    public void offer(int val) {
        if(isFull()) {
            //扩容
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;//11
        //向上调整
        shiftUp(usedSize-1);//10
    }

    public boolean isFull() {
        return usedSize == elem.length;
    }

    //注意堆删除的一定是堆顶的元素
    public void pop() {
        if(isEmpty()) {
            return;
        }
        //交换堆顶和最后一个元素
        swap(0,usedSize - 1);
        usedSize--;
        // 堆顶元素进行向下调整
        shiftDown(0,usedSize);
    }
    //进行交换
    private void swap(int child,int parent) {
        int tmp = elem[child];
        elem[child] = elem[parent];
        elem[parent] = tmp;

    }
    public boolean isEmpty() {
        return usedSize == 0;
    }


    /**
     * 前K个最大的元素  top-k 思路 ：
     *      思路 ： 1. 求前k个最大元素，建立小根堆
     *             2.  把数组前k个元素offer到堆中
     *             3.  从第k + 1 个元素开始遍历，比较堆顶元素和数组元素
     *             4.  如果数组元素比堆顶元素小，不做调整
     *                 若数组元素比堆顶元素大，则弹出堆顶元素，添加这个数组元素到堆中
     *                 (思路就是： 小根堆中堆顶元素是 k 个 中最小的，若数组元素比堆顶元素大，
     *                 说明堆顶元素不是前k个中最大的元素)
     * N*logK
     */
    public static int[] maxK(int[] arr, int k) {
        Queue<Integer> minHeap = new PriorityQueue<>(k);
        //把数组前k个元素offer到堆中  K * logK
        for (int i = 0; i < k; i++) {
            minHeap.offer(arr[i]);
        }
        //从第k + 1 个元素开始遍历，比较堆顶元素和数组元素
        // 堆顶元素 小的时候，就出堆。  (N-K) * Logk
        for (int i = k; i < arr.length; i++) {
            if(arr[i] > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(arr[i]);
            }
        }
        //弹出堆中元素到数组中去
        int[] ret = new int[k];
        int i = 0;
        while (!minHeap.isEmpty()) {
            ret[i] = minHeap.poll();
            i++;
        }
        return ret;
    }

    //力扣17.14. 求数组中最小的k个数 (中等题目) (top-k 的思路 ： 建立一个大根堆)
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null && 0 == k) {
            return ret;
        }
        //利用匿名内部类的方式来创建一个大根堆
        Queue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);  //这就是大根堆了
            }
        });
        //把数组前k个元素offer到堆中  K * logK
        for (int i = 0; i < k; i++) {
            maxHeap.offer(arr[i]);
        }
        //从第k + 1 个元素开始遍历，比较堆顶元素和数组元素
        // 堆顶元素 小的时候，就出堆。  (N-K) * Logk
        for (int i = k; i < arr.length; i++) {
            if(arr[i] < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
        }
        //弹出堆中元素到数组中去
        int i = 0;
        while (!maxHeap.isEmpty()) {
            ret[i] = maxHeap.poll();
            i++;
        }
        return ret;
    }


    /**
     * 堆排序
     * 时间复杂度：n*logn  ，每一个节点都要进行向下调整，     冒泡排序时间复杂度是 N ^ 2
     * 调整次数为 树的高度 h = log N   N为节点数，共有N个节点，
     * 所以时间复杂度就是总的调整次数为 n*logn
     * 空间复杂度：O(1)
     */
    //从小到大排序，建立大根堆， (若是建立小根堆，则左右孩子不能比较出大小，
    // 并且要求只能是在数组本身上调整，所以也就不能建立小根堆依次弹出，再放到数组中去了)
    public void heapSort() {
        int end = usedSize - 1; //用于记录最后一个节点下标
        //循环条件就是end一直到0下标处
        //注意此处已经是大根堆了
        while (end > 0) {
            //交换
            swap(0,end);
            //注意向下调整的结束下标：是节点个数
            shiftDown(0,end);   //注意不能是usedSize - 1 ，因为usedSize是数组中的数据，大小是不会变的
                                       //而这里的end代表的是未排序好的数据
            end--;
        }
    }

    //力扣692.前k个高频单词(中等题目)
    public List<String> topKFrequent(String[] words, int k) {
        //1、遍历数组 统计每个单词出现的频率
        Map<String,Integer> hashMap = new HashMap<>();
        for (String s : words) {
            hashMap.put(s,hashMap.getOrDefault(s,0) + 1);
        }

        //2.相当于求前k大的，要建立小根堆
        /**
         *   注意这里我们要进行比较的是Map.Entry<String,Integer>中的次数进行比较，
         *   所以我们要传入一个比较器
         */
        Queue<Map.Entry<String,Integer>> minHeap = new PriorityQueue(k,new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    //如果次数相等的话，则进行比较字母前后，也就相当于建了一个大根堆
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });


        //遍历hashMap
        for (Map.Entry<String, Integer> entry: hashMap.entrySet()) {
            /**
             * 特别注意，这里是<k   而不是小于等于，因为size = 0的时候就执行了一次offer了
             */
            if (minHeap.size() < k) {
                minHeap.offer(entry);   //放入了前k个元素
            } else {
                Map.Entry<String, Integer> top = minHeap.peek();
                //如果堆顶元素次数小于遍历的，则进行替换
                if(top.getValue().compareTo(entry.getValue()) < 0 ) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }else {
                    //这是次数相同的情况下，进行比较单词
                    //Map.Entry<String, Integer> top = minHeap.peek();
                    if (top.getValue().compareTo(entry.getValue()) == 0) {
                        if(top.getKey().compareTo(entry.getKey()) > 0) {
                            //如果遍历到的单词字母靠前的话，则与堆顶元素进行替换
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }
        //走到这之后，小根堆中已经有了元素，依次弹出到一个数组中去
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String ch = minHeap.poll().getKey();
            list.add(ch);
        }
        //注意这是小根堆进行弹出的，所以是从小到大的，要进行反转，变成从大到小的
        Collections.reverse(list);   //这是一个专门处理集合的，类似于Arrays去处理数组的
        return list;
    }


    //力扣692.前k个高频单词(中等题目)  用peek
    public List<String> topKFrequent2(String[] words, int k) {
        //1、遍历数组 统计每个单词出现的频率
        Map<String,Integer> hashMap = new HashMap<>();
        for (String s : words) {
            hashMap.put(s,hashMap.getOrDefault(s,0) + 1);
        }

        //2.相当于求前k大的，要建立小根堆
        /**
         *   注意这里我们要进行比较的是Map.Entry<String,Integer>中的次数进行比较，
         *   所以我们要传入一个比较器
         */
        Queue<Map.Entry<String,Integer>> minHeap = new PriorityQueue(k,new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    //如果次数相等的话，则进行比较字母前后，也就相当于建了一个大根堆
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });


        //遍历hashMap
        for (Map.Entry<String, Integer> entry: hashMap.entrySet()) {
            /**
             * 特别注意，这里是<k   而不是小于等于，因为size = 0的时候就执行了一次offer了
             */
            if (minHeap.size() < k) {
                minHeap.offer(entry);   //放入了前k个元素
            } else {
                //Map.Entry<String, Integer> top = minHeap.peek();
                //如果堆顶元素次数小于遍历的，则进行替换
                if(minHeap.peek().getValue().compareTo(entry.getValue()) < 0 ) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }else {
                    //这是次数相同的情况下，进行比较单词
                    //Map.Entry<String, Integer> top = minHeap.peek();
                    if (minHeap.peek().getValue().compareTo(entry.getValue()) == 0) {
                        if(minHeap.peek().getKey().compareTo(entry.getKey()) > 0) {
                            //如果遍历到的单词字母靠前的话，则与堆顶元素进行替换
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }
        //走到这之后，小根堆中已经有了元素，依次弹出到一个数组中去
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String ch = minHeap.poll().getKey();
            list.add(ch);
        }
        //注意这是小根堆进行弹出的，所以是从小到大的，要进行反转，变成从大到小的
        Collections.reverse(list);   //这是一个专门处理集合的，类似于Arrays去处理数组的
        return list;
    }
}
